package com.wtgroup.demo.leetcode.q033_搜索旋转排序数组;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/11 12:05
 */
public class Q033_My {

    public static void main(String[] args) {
        int[][] inputs = {
                // {4, 5, 6, 7, 0, 1, 2},
                // {4, 5, 6, 7, 0, 1, 2},
                // {1},
                // {8},
                // {1, 3},
                {1, 3, 5}
        };
        int[] targets = {/*0, 3, 0, 8, 3, */5};
        Q033_My exe = new Q033_My();
        for (int i = 0; i < inputs.length; i++) {
            int res = exe.search(inputs[i], targets[i]);
            System.out.println(res);
        }
    }


    /**
     * [思路]
     * 1. 找到自小元素位置 (x_0 位置).
     * 2. 两侧选一侧二分查找 target
     *
     * 注意, x_0 == 0 的特殊情形.
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n ==0) {
            return -1;
        }
        if (n ==1) {
            return nums[0] == target ? 0 : -1;
        }

        // 找到 x_1 下标
        int x0 = searchX0(nums);

        // 二分查找 target
        if (target < nums[0] && target > nums[n - 1]) {
            return -1; // 必不在
        }

        // 考虑特殊情形: 0 位旋转, x0-1=-1
        if (target >= nums[0]) {
            // 左侧二分查找
            return biSearch(nums, target, 0, x0 == 0 ? n - 1 : x0);
        } else {
            // 右侧二分查找
            return biSearch(nums, target, x0, n - 1);
        }
    }

    private int searchX0(int[] nums) {
        if (nums.length==1) {
            return 0;
        }

        int left = 0; int right = nums.length -1;
        while (right-left>1) { // 2 元素时停
            int mid = (left + right) / 2;
            // 3 种
            if(nums[left] < nums[right]) {
                // L<R, 则 M 必在其中间 -> 原序列全体旋转
                return 0;
            }
            if (nums[left] < nums[mid]) {
                // mid 必位于 [xk, xn-1] => x0 必在 mid 右侧
                left = mid;
            } else {
                // mid 必位于 [x0, xk-1] => x0 必在 mid 左侧
                right = mid;
            }
        }

        return nums[left] > nums[right] ? right : left;
    }

    private int biSearch(int[] nums, int target, int left, int right) {

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}
